/*
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
*/

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total = m+n;
        if (total % 2) return (double)find_kth(A, m, B, n, (total+1)/2);
        return (double)(find_kth(A, m, B, n, total/2)+find_kth(A, m, B, n, total/2+1))/2.0;
    }
private:
    // find the kth number in A and B
    int find_kth(int A[], int m, int B[], int n, int k) {
        if (m == 0) return B[k-1];
        if (n == 0) return A[k-1];
        if (k == 1) return min(A[0], B[0]);
        int idx_a, idx_b;
        if (m < n) {idx_a = min(k/2, m)-1; idx_b = k-2-idx_a;} 
        else {idx_b = min(k/2,n)-1; idx_a = k-2-idx_b;}
        if (A[idx_a] == B[idx_b]) return A[idx_a];
        if (A[idx_a] < B[idx_b]) return find_kth(A+idx_a+1, m-idx_a-1, B, n, k-idx_a-1);
        return find_kth(A, m, B+idx_b+1, n-idx_b-1, k-idx_b-1);
    }
};
